﻿#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution
{
    unordered_map<int, int> hash;
public:
    // 452. 用最少数量的箭引爆气球
    int findMinArrowShots(vector<vector<int>>& points)
    {
        sort(points.begin(), points.end());
        int right = points[0][1], ret = 1;
        for (int i = 1; i < points.size(); ++i)
        {
            int a = points[i][0], b = points[i][1];
            if (a <= right)
            {
                right = min(right, b);
            }
            else
            {
                ret++;
                right = b;
            }
        }
        return ret;
    }

    // 397. 整数替换
    // 递归+记忆化搜索
    /*int integerReplacement(int n)
    {
        return dfs(n);
    }

    int dfs(long long n)
    {
        if (hash.count(n))
            return hash[n];

        if (n == 1)
        {
            hash[1] = 0;
            return 0;
        }

        if (n % 2 == 0)
        {
            hash[n] = 1 + dfs(n / 2);
            return hash[n];
        }
        else
        {
            hash[n] = 1 + min(dfs(n + 1), dfs(n - 1));
            return hash[n];
        }
    }*/

    // 贪心
    int integerReplacement(int n)
    {
        int ret = 0;
        while (n > 1)
        {
            if (n % 2 == 0)
            {
                n /= 2;
                ret++;
            }
            else
            {
                if (n == 3)
                {
                    n = 1;
                    ret += 2;
                }
                else if (n % 4 == 1)
                {
                    n /= 2;
                    ret += 2;
                }
                else
                {
                    n = n / 2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
};

int main()
{
    /*vector<vector<int>> v{ {10,16},{2,8},{1,6},{7,12} };
    cout << Solution().findMinArrowShots(v) << endl;*/

    cout << Solution().integerReplacement(95) << endl;

    return 0;
}